package com.yangzhe.algorithm.c039;

import java.util.Map;
import java.util.TreeMap;

// 含有嵌套的分子式求原子数量
// 测试链接 : https://leetcode.cn/problems/number-of-atoms/
public class Code03_NumberOfAtoms {

    public static int where = 0;

    /**
     * 变量设计：
     * 1. resultMap：存储当前递归元素总表
     * 2. cur：存储当前递归过程单个的元素
     * 3. curMap：存储子递归过程返回的元素表
     * 4. times: 收集遇到的数字
     * <p>
     * 5. where：递归进行到哪个位置
     * <p>
     * 递归过程，每轮必定以)或终止位置结束：
     * 1. 遇到大写字母：填表，并把大写字母覆盖到cur，清空curMap
     * 2. 遇到小写字母：追加到cur
     * 3. 遇到数字：times = times * 10 + c - '0'
     * 4. 遇到(：填表，开启递归子过程，返回值给curMap
     * 5. 遇到)或终止：填表，设置where位置，并返回表
     * <p>
     * 填表：
     * 1. 如果times=0，代表数字被省略了，设置成1
     * 2. 把上一个cur和curMap按times收集到resultMap中
     *
     * @param formula
     * @return
     */
    public String countOfAtoms(String formula) {
        where = 0;
        Map<String, Integer> resultMap = f(formula, 0);
        StringBuilder builder = new StringBuilder();
        for (Map.Entry<String, Integer> resultEntry : resultMap.entrySet()) {

            builder.append(resultEntry.getKey());
            if (resultEntry.getValue() > 1) {
                builder.append(resultEntry.getValue());
            }
        }

        return builder.toString();
    }

    public Map<String, Integer> f(String formula, int i) {
        // 用TreeMap是有序的，默认的Comparator就是题目要求的字典序
        Map<String, Integer> resultMap = new TreeMap<>();
        StringBuilder cur = new StringBuilder();
        Map<String, Integer> curMap = new TreeMap<>();
        int times = 0;
        while (i < formula.length()) {
            char c = formula.charAt(i);

            if ((c >= 'A' && c <= 'Z') || c == '(') {
                fill(resultMap, cur, curMap, times);
                // 初始化
                cur.setLength(0);
                times = 0;
                curMap = new TreeMap<>();

                if (c >= 'A' && c <= 'Z') {
                    cur.append(c);
                } else if (c == '(') {
                    curMap = f(formula, i + 1);
                    i = where;
                }
            } else if (c >= 'a' && c <= 'z') {
                cur.append(c);
            } else if (c >= '0' && c <= '9') {
                times = times * 10 + c - '0';
            } else if (c == ')') {
                break;
            }

            i++;
        }

        fill(resultMap, cur, curMap, times);
        where = i;

        return resultMap;
    }

    public void fill(Map<String, Integer> resultMap, StringBuilder cur, Map<String, Integer> curMap, int times) {
        // 因为只有1的时候数字被忽略，所以设置成1
        times = times == 0 ? 1 : times;

        if (cur.length() > 0) {
            Integer preCount = 0;
            if (resultMap.containsKey(cur.toString())) {
                preCount = resultMap.get(cur.toString());
            }
            resultMap.put(cur.toString(), preCount + times);
        }

        for (Map.Entry<String, Integer> curMapEntry : curMap.entrySet()) {
            Integer preCount = 0;
            if (resultMap.containsKey(curMapEntry.getKey())) {
                preCount = resultMap.get(curMapEntry.getKey());
            }
            resultMap.put(curMapEntry.getKey(), preCount + curMapEntry.getValue() * times);
        }
    }

    public static void main(String[] args) {
        Code03_NumberOfAtoms num = new Code03_NumberOfAtoms();
        System.out.println(num.countOfAtoms("A3A2(AB2)2Ma"));
    }
}
